package NowCoder.Greed;
import java.util.*;

/**
 * OR57 手套
 * 中等  通过率：25.28%  时间限制：3秒  空间限制：32M
 * 知识点 模拟 贪心
 * 描述
 * 在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。
 * A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。
 * 所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。
 *
 * 给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,
 * 分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。
 *
 * 测试样例：
 * 4,[0,7,1,6],[1,5,0,6]
 * 返回：10(解释：可以左手手套取2只，右手手套取8只)
 * https://www.nowcoder.com/practice/365d5722fff640a0b6684391153e58d8?tpId=182&tqId=34783&ru=/exam/oj
 */
public class 手套_OR57 {
    public int findMinimum(int n, int[] left, int[] right) {
        // write code here
        /**
         1.要想能够让左右手套至少有一副配对,我们可以先把左手手套每种都至少拿一只,然后再随便拿一只右手手套就可以成功配对
         2.先计算出左手和右手手套的总数,然后减去各自的最少的数再加一,这样就可以保证取出的手套至少每种都有一只.
         3.比较两者较小的那个数,决定先取左手还是先取右手.
         4.最后再加上另一钟手套的随便一只
         */
        int sum=0;//存放某种颜色的一只手的手套个数为0的时候，另一只手的手套数量
        int leftSum=0;
        int rightSum=0;
        int leftMin=Integer.MAX_VALUE;
        int rightMin=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            if(left[i]*right[i]==0){
                sum=sum+left[i]+right[i];
            }else{
                leftSum+=left[i];
                if(leftMin>left[i]){
                    leftMin=left[i];
                }
                rightSum+=right[i];
                if(rightMin>right[i]){
                    rightMin=right[i];
                }
            }
        }
        return sum+Math.min(leftSum-leftMin+1,rightSum-rightMin+1)+1;
    }
}
